/*
 * Copyright (c) 2007, 2015, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
/*
 * Copyright 2002-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
/*
 * $Id: NodeSequence.java,v 1.6 2007/01/12 19:26:42 spericas Exp $
 */
package com.sun.org.apache.xpath.internal.axes;

import java.util.Vector;

import com.sun.org.apache.xml.internal.dtm.DTM;
import com.sun.org.apache.xml.internal.dtm.DTMFilter;
import com.sun.org.apache.xml.internal.dtm.DTMIterator;
import com.sun.org.apache.xml.internal.dtm.DTMManager;
import com.sun.org.apache.xml.internal.utils.NodeVector;
import com.sun.org.apache.xpath.internal.NodeSetDTM;
import com.sun.org.apache.xpath.internal.XPathContext;
import com.sun.org.apache.xpath.internal.objects.XObject;

/**
 * This class is the dynamic wrapper for a Xalan DTMIterator instance, and
 * provides random access capabilities.
 */
public class NodeSequence extends XObject
    implements DTMIterator, Cloneable, PathComponent {

  static final long serialVersionUID = 3866261934726581044L;
  /**
   * The index of the last node in the iteration.
   */
  protected int m_last = -1;

  /**
   * The index of the next node to be fetched.  Useful if this
   * is a cached iterator, and is being used as random access
   * NodeList.
   */
  protected int m_next = 0;

  /**
   * A cache of a list of nodes obtained from the iterator so far.
   * This list is appended to until the iterator is exhausted and
   * the cache is complete.
   * <p>
   * Multiple NodeSequence objects may share the same cache.
   */
  private IteratorCache m_cache;

  /**
   * If this iterator needs to cache nodes that are fetched, they
   * are stored in the Vector in the generic object.
   */
  protected NodeVector getVector() {
    NodeVector nv = (m_cache != null) ? m_cache.getVector() : null;
    return nv;
  }

  /**
   * Get the cache (if any) of nodes obtained from
   * the iterator so far. Note that the cache keeps
   * growing until the iterator is walked to exhaustion,
   * at which point the cache is "complete".
   */
  private IteratorCache getCache() {
    return m_cache;
  }

  /**
   * Set the vector where nodes will be cached.
   */
  protected void SetVector(NodeVector v) {
    setObject(v);
  }


  /**
   * If the iterator needs to cache nodes as they are fetched,
   * then this method returns true.
   */
  public boolean hasCache() {
    final NodeVector nv = getVector();
    return (nv != null);
  }

  /**
   * If this NodeSequence has a cache, and that cache is
   * fully populated then this method returns true, otherwise
   * if there is no cache or it is not complete it returns false.
   */
  private boolean cacheComplete() {
    final boolean complete;
    if (m_cache != null) {
      complete = m_cache.isComplete();
    } else {
      complete = false;
    }
    return complete;
  }

  /**
   * If this NodeSequence has a cache, mark that it is complete.
   * This method should be called after the iterator is exhausted.
   */
  private void markCacheComplete() {
    NodeVector nv = getVector();
    if (nv != null) {
      m_cache.setCacheComplete(true);
    }
  }


  /**
   * The functional iterator that fetches nodes.
   */
  protected DTMIterator m_iter;

  /**
   * Set the functional iterator that fetches nodes.
   *
   * @param iter The iterator that is to be contained.
   */
  public final void setIter(DTMIterator iter) {
    m_iter = iter;
  }

  /**
   * Get the functional iterator that fetches nodes.
   *
   * @return The contained iterator.
   */
  public final DTMIterator getContainedIter() {
    return m_iter;
  }

  /**
   * The DTMManager to use if we're using a NodeVector only.
   * We may well want to do away with this, and store it in the NodeVector.
   */
  protected DTMManager m_dtmMgr;

  // ==== Constructors ====

  /**
   * Create a new NodeSequence from a (already cloned) iterator.
   *
   * @param iter Cloned (not static) DTMIterator.
   * @param context The initial context node.
   * @param xctxt The execution context.
   * @param shouldCacheNodes True if this sequence can random access.
   */
  private NodeSequence(DTMIterator iter, int context, XPathContext xctxt,
      boolean shouldCacheNodes) {
    setIter(iter);
    setRoot(context, xctxt);
    setShouldCacheNodes(shouldCacheNodes);
  }

  /**
   * Create a new NodeSequence from a (already cloned) iterator.
   */
  public NodeSequence(Object nodeVector) {
    super(nodeVector);
    if (nodeVector instanceof NodeVector) {
      SetVector((NodeVector) nodeVector);
    }
    if (null != nodeVector) {
      assertion(nodeVector instanceof NodeVector,
          "Must have a NodeVector as the object for NodeSequence!");
      if (nodeVector instanceof DTMIterator) {
        setIter((DTMIterator) nodeVector);
        m_last = ((DTMIterator) nodeVector).getLength();
      }

    }
  }

  /**
   * Construct an empty XNodeSet object.  This is used to create a mutable
   * nodeset to which random nodes may be added.
   */
  private NodeSequence(DTMManager dtmMgr) {
    super(new NodeVector());
    m_last = 0;
    m_dtmMgr = dtmMgr;
  }


  /**
   * Create a new NodeSequence in an invalid (null) state.
   */
  public NodeSequence() {
    return;
  }


  /**
   * @see DTMIterator#getDTM(int)
   */
  public DTM getDTM(int nodeHandle) {
    DTMManager mgr = getDTMManager();
    if (null != mgr) {
      return getDTMManager().getDTM(nodeHandle);
    } else {
      assertion(false, "Can not get a DTM Unless a DTMManager has been set!");
      return null;
    }
  }

  /**
   * @see DTMIterator#getDTMManager()
   */
  public DTMManager getDTMManager() {
    return m_dtmMgr;
  }

  /**
   * @see DTMIterator#getRoot()
   */
  public int getRoot() {
    if (null != m_iter) {
      return m_iter.getRoot();
    } else {
      // NodeSetDTM will call this, and so it's not a good thing to throw
      // an assertion here.
      // assertion(false, "Can not get the root from a non-iterated NodeSequence!");
      return DTM.NULL;
    }
  }

  /**
   * @see DTMIterator#setRoot(int, Object)
   */
  public void setRoot(int nodeHandle, Object environment) {
    // If root is DTM.NULL, then something's wrong with the context
    if (nodeHandle == DTM.NULL) {
      throw new RuntimeException("Unable to evaluate expression using " +
          "this context");
    }

    if (null != m_iter) {
      XPathContext xctxt = (XPathContext) environment;
      m_dtmMgr = xctxt.getDTMManager();
      m_iter.setRoot(nodeHandle, environment);
      if (!m_iter.isDocOrdered()) {
        if (!hasCache()) {
          setShouldCacheNodes(true);
        }
        runTo(-1);
        m_next = 0;
      }
    } else {
      assertion(false, "Can not setRoot on a non-iterated NodeSequence!");
    }
  }

  /**
   * @see DTMIterator#reset()
   */
  public void reset() {
    m_next = 0;
    // not resetting the iterator on purpose!!!
  }

  /**
   * @see DTMIterator#getWhatToShow()
   */
  public int getWhatToShow() {
    return hasCache() ? (DTMFilter.SHOW_ALL & ~DTMFilter.SHOW_ENTITY_REFERENCE)
        : m_iter.getWhatToShow();
  }

  /**
   * @see DTMIterator#getExpandEntityReferences()
   */
  public boolean getExpandEntityReferences() {
    if (null != m_iter) {
      return m_iter.getExpandEntityReferences();
    } else {
      return true;
    }
  }

  /**
   * @see DTMIterator#nextNode()
   */
  public int nextNode() {
    // If the cache is on, and the node has already been found, then
    // just return from the list.
    NodeVector vec = getVector();
    if (null != vec) {
      // There is a cache
      if (m_next < vec.size()) {
        // The node is in the cache, so just return it.
        int next = vec.elementAt(m_next);
        m_next++;
        return next;
      } else if (cacheComplete() || (-1 != m_last) || (null == m_iter)) {
        m_next++;
        return DTM.NULL;
      }
    }

    if (null == m_iter) {
      return DTM.NULL;
    }

    int next = m_iter.nextNode();
    if (DTM.NULL != next) {
      if (hasCache()) {
        if (m_iter.isDocOrdered()) {
          getVector().addElement(next);
          m_next++;
        } else {
          int insertIndex = addNodeInDocOrder(next);
          if (insertIndex >= 0) {
            m_next++;
          }
        }
      } else {
        m_next++;
      }
    } else {
      // We have exhausted the iterator, and if there is a cache
      // it must have all nodes in it by now, so let the cache
      // know that it is complete.
      markCacheComplete();

      m_last = m_next;
      m_next++;
    }

    return next;
  }

  /**
   * @see DTMIterator#previousNode()
   */
  public int previousNode() {
    if (hasCache()) {
      if (m_next <= 0) {
        return DTM.NULL;
      } else {
        m_next--;
        return item(m_next);
      }
    } else {
      int n = m_iter.previousNode();
      m_next = m_iter.getCurrentPos();
      return m_next;
    }
  }

  /**
   * @see DTMIterator#detach()
   */
  public void detach() {
    if (null != m_iter) {
      m_iter.detach();
    }
    super.detach();
  }

  /**
   * Calling this with a value of false will cause the nodeset
   * to be cached.
   *
   * @see DTMIterator#allowDetachToRelease(boolean)
   */
  public void allowDetachToRelease(boolean allowRelease) {
    if ((false == allowRelease) && !hasCache()) {
      setShouldCacheNodes(true);
    }

    if (null != m_iter) {
      m_iter.allowDetachToRelease(allowRelease);
    }
    super.allowDetachToRelease(allowRelease);
  }

  /**
   * @see DTMIterator#getCurrentNode()
   */
  public int getCurrentNode() {
    if (hasCache()) {
      int currentIndex = m_next - 1;
      NodeVector vec = getVector();
      if ((currentIndex >= 0) && (currentIndex < vec.size())) {
        return vec.elementAt(currentIndex);
      } else {
        return DTM.NULL;
      }
    }

    if (null != m_iter) {
      return m_iter.getCurrentNode();
    } else {
      return DTM.NULL;
    }
  }

  /**
   * @see DTMIterator#isFresh()
   */
  public boolean isFresh() {
    return (0 == m_next);
  }

  /**
   * @see DTMIterator#setShouldCacheNodes(boolean)
   */
  public void setShouldCacheNodes(boolean b) {
    if (b) {
      if (!hasCache()) {
        SetVector(new NodeVector());
      }
//        else
//          getVector().RemoveAllNoClear();  // Is this good?
    } else {
      SetVector(null);
    }
  }

  /**
   * @see DTMIterator#isMutable()
   */
  public boolean isMutable() {
    return hasCache(); // though may be surprising if it also has an iterator!
  }

  /**
   * @see DTMIterator#getCurrentPos()
   */
  public int getCurrentPos() {
    return m_next;
  }

  /**
   * @see DTMIterator#runTo(int)
   */
  public void runTo(int index) {
    int n;

    if (-1 == index) {
      int pos = m_next;
      while (DTM.NULL != (n = nextNode())) {
        ;
      }
      m_next = pos;
    } else if (m_next == index) {
      return;
    } else if (hasCache() && index < getVector().size()) {
      m_next = index;
    } else if ((null == getVector()) && (index < m_next)) {
      while ((m_next >= index) && DTM.NULL != (n = previousNode())) {
        ;
      }
    } else {
      while ((m_next < index) && DTM.NULL != (n = nextNode())) {
        ;
      }
    }

  }

  /**
   * @see DTMIterator#setCurrentPos(int)
   */
  public void setCurrentPos(int i) {
    runTo(i);
  }

  /**
   * @see DTMIterator#item(int)
   */
  public int item(int index) {
    setCurrentPos(index);
    int n = nextNode();
    m_next = index;
    return n;
  }

  /**
   * @see DTMIterator#setItem(int, int)
   */
  public void setItem(int node, int index) {
    NodeVector vec = getVector();
    if (null != vec) {
      int oldNode = vec.elementAt(index);
      if (oldNode != node && m_cache.useCount() > 1) {
            /* If we are going to set the node at the given index
             * to a different value, and the cache is shared
             * (has a use count greater than 1)
             * then make a copy of the cache and use it
             * so we don't overwrite the value for other
             * users of the cache.
             */
        IteratorCache newCache = new IteratorCache();
        final NodeVector nv;
        try {
          nv = (NodeVector) vec.clone();
        } catch (CloneNotSupportedException e) {
          // This should never happen
          e.printStackTrace();
          RuntimeException rte = new RuntimeException(e.getMessage());
          throw rte;
        }
        newCache.setVector(nv);
        newCache.setCacheComplete(true);
        m_cache = newCache;
        vec = nv;

        // Keep our superclass informed of the current NodeVector
        super.setObject(nv);

            /* When we get to here the new cache has
             * a use count of 1 and when setting a
             * bunch of values on the same NodeSequence,
             * such as when sorting, we will keep setting
             * values in that same copy which has a use count of 1.
             */
      }
      vec.setElementAt(node, index);
      m_last = vec.size();
    } else {
      m_iter.setItem(node, index);
    }
  }

  /**
   * @see DTMIterator#getLength()
   */
  public int getLength() {
    IteratorCache cache = getCache();

    if (cache != null) {
      // Nodes from the iterator are cached
      if (cache.isComplete()) {
        // All of the nodes from the iterator are cached
        // so just return the number of nodes in the cache
        NodeVector nv = cache.getVector();
        return nv.size();
      }

      // If this NodeSequence wraps a mutable nodeset, then
      // m_last will not reflect the size of the nodeset if
      // it has been mutated...
      if (m_iter instanceof NodeSetDTM) {
        return m_iter.getLength();
      }

      if (-1 == m_last) {
        int pos = m_next;
        runTo(-1);
        m_next = pos;
      }
      return m_last;
    } else {
      return (-1 == m_last) ? (m_last = m_iter.getLength()) : m_last;
    }
  }

  /**
   * Note: Not a deep clone.
   *
   * @see DTMIterator#cloneWithReset()
   */
  public DTMIterator cloneWithReset() throws CloneNotSupportedException {
    NodeSequence seq = (NodeSequence) super.clone();
    seq.m_next = 0;
    if (m_cache != null) {
      // In making this clone of an iterator we are making
      // another NodeSequence object it has a reference
      // to the same IteratorCache object as the original
      // so we need to remember that more than one
      // NodeSequence object shares the cache.
      m_cache.increaseUseCount();
    }

    return seq;
  }

  /**
   * Get a clone of this iterator, but don't reset the iteration in the
   * process, so that it may be used from the current position.
   * Note: Not a deep clone.
   *
   * @return A clone of this object.
   */
  public Object clone() throws CloneNotSupportedException {
    NodeSequence clone = (NodeSequence) super.clone();
    if (null != m_iter) {
      clone.m_iter = (DTMIterator) m_iter.clone();
    }
    if (m_cache != null) {
      // In making this clone of an iterator we are making
      // another NodeSequence object it has a reference
      // to the same IteratorCache object as the original
      // so we need to remember that more than one
      // NodeSequence object shares the cache.
      m_cache.increaseUseCount();
    }

    return clone;
  }


  /**
   * @see DTMIterator#isDocOrdered()
   */
  public boolean isDocOrdered() {
    if (null != m_iter) {
      return m_iter.isDocOrdered();
    } else {
      return true; // can't be sure?
    }
  }

  /**
   * @see DTMIterator#getAxis()
   */
  public int getAxis() {
    if (null != m_iter) {
      return m_iter.getAxis();
    } else {
      assertion(false, "Can not getAxis from a non-iterated node sequence!");
      return 0;
    }
  }

  /**
   * @see PathComponent#getAnalysisBits()
   */
  public int getAnalysisBits() {
    if ((null != m_iter) && (m_iter instanceof PathComponent)) {
      return ((PathComponent) m_iter).getAnalysisBits();
    } else {
      return 0;
    }
  }

  /**
   * @see org.apache.xpath.Expression#fixupVariables(Vector, int)
   */
  public void fixupVariables(Vector vars, int globalsSize) {
    super.fixupVariables(vars, globalsSize);
  }

  /**
   * Add the node into a vector of nodes where it should occur in
   * document order.
   *
   * @param node The node to be added.
   * @return insertIndex.
   * @throws RuntimeException thrown if this NodeSetDTM is not of a mutable type.
   */
  protected int addNodeInDocOrder(int node) {
    assertion(hasCache(), "addNodeInDocOrder must be done on a mutable sequence!");

    int insertIndex = -1;

    NodeVector vec = getVector();

    // This needs to do a binary search, but a binary search
    // is somewhat tough because the sequence test involves
    // two nodes.
    int size = vec.size(), i;

    for (i = size - 1; i >= 0; i--) {
      int child = vec.elementAt(i);

      if (child == node) {
        i = -2; // Duplicate, suppress insert

        break;
      }

      DTM dtm = m_dtmMgr.getDTM(node);
      if (!dtm.isNodeAfter(node, child)) {
        break;
      }
    }

    if (i != -2) {
      insertIndex = i + 1;

      vec.insertElementAt(node, insertIndex);
    }

    // checkDups();
    return insertIndex;
  } // end addNodeInDocOrder(Vector v, Object obj)

  /**
   * It used to be that many locations in the code simply
   * did an assignment to this.m_obj directly, rather than
   * calling the setObject(Object) method. The problem is
   * that our super-class would be updated on what the
   * cache associated with this NodeSequence, but
   * we wouldn't know ourselves.
   * <p>
   * All setting of m_obj is done through setObject() now,
   * and this method over-rides the super-class method.
   * So now we are in the loop have an opportunity
   * to update some caching information.
   */
  protected void setObject(Object obj) {
    if (obj instanceof NodeVector) {
      // Keep our superclass informed of the current NodeVector
      // ... if we don't the smoketest fails (don't know why).
      super.setObject(obj);

      // A copy of the code of what SetVector() would do.
      NodeVector v = (NodeVector) obj;
      if (m_cache != null) {
        m_cache.setVector(v);
      } else if (v != null) {
        m_cache = new IteratorCache();
        m_cache.setVector(v);
      }
    } else if (obj instanceof IteratorCache) {
      IteratorCache cache = (IteratorCache) obj;
      m_cache = cache;
      m_cache.increaseUseCount();

      // Keep our superclass informed of the current NodeVector
      super.setObject(cache.getVector());
    } else {
      super.setObject(obj);
    }

  }

  /**
   * Each NodeSequence object has an iterator which is "walked".
   * As an iterator is walked one obtains nodes from it.
   * As those nodes are obtained they may be cached, making
   * the next walking of a copy or clone of the iterator faster.
   * This field (m_cache) is a reference to such a cache,
   * which is populated as the iterator is walked.
   * <p>
   * Note that multiple NodeSequence objects may hold a
   * reference to the same cache, and also
   * (and this is important) the same iterator.
   * The iterator and its cache may be shared among
   * many NodeSequence objects.
   * <p>
   * If one of the NodeSequence objects walks ahead
   * of the others it fills in the cache.
   * As the others NodeSequence objects catch up they
   * get their values from
   * the cache rather than the iterator itself, so
   * the iterator is only ever walked once and everyone
   * benefits from the cache.
   * <p>
   * At some point the cache may be
   * complete due to walking to the end of one of
   * the copies of the iterator, and the cache is
   * then marked as "complete".
   * and the cache will have no more nodes added to it.
   * <p>
   * Its use-count is the number of NodeSequence objects that use it.
   */
  private final static class IteratorCache {

    /**
     * A list of nodes already obtained from the iterator.
     * As the iterator is walked the nodes obtained from
     * it are appended to this list.
     * <p>
     * Both an iterator and its corresponding cache can
     * be shared by multiple NodeSequence objects.
     * <p>
     * For example, consider three NodeSequence objects
     * ns1, ns2 and ns3 doing such sharing, and the
     * nodes to be obtaind from the iterator being
     * the sequence { 33, 11, 44, 22, 55 }.
     * <p>
     * If ns3.nextNode() is called 3 times the the
     * underlying iterator will have walked through
     * 33, 11, 55 and these three nodes will have been put
     * in the cache.
     * <p>
     * If ns2.nextNode() is called 2 times it will return
     * 33 and 11 from the cache, leaving the iterator alone.
     * <p>
     * If ns1.nextNode() is called 6 times it will return
     * 33 and 11 from the cache, then get 44, 22, 55 from
     * the iterator, and appending 44, 22, 55 to the cache.
     * On the sixth call it is found that the iterator is
     * exhausted and the cache is marked complete.
     * <p>
     * Should ns2 or ns3 have nextNode() called they will
     * know that the cache is complete, and they will
     * obtain all subsequent nodes from the cache.
     * <p>
     * Note that the underlying iterator, though shared
     * is only ever walked once.
     */
    private NodeVector m_vec2;

    /**
     * true if the associated iterator is exhausted and
     * all nodes obtained from it are in the cache.
     */
    private boolean m_isComplete2;

    private int m_useCount2;

    IteratorCache() {
      m_vec2 = null;
      m_isComplete2 = false;
      m_useCount2 = 1;
      return;
    }

    /**
     * Returns count of how many NodeSequence objects share this
     * IteratorCache object.
     */
    private int useCount() {
      return m_useCount2;
    }

    /**
     * This method is called when yet another
     * NodeSequence object uses, or shares
     * this same cache.
     */
    private void increaseUseCount() {
      if (m_vec2 != null) {
        m_useCount2++;
      }

    }

    /**
     * Sets the NodeVector that holds the
     * growing list of nodes as they are appended
     * to the cached list.
     */
    private void setVector(NodeVector nv) {
      m_vec2 = nv;
      m_useCount2 = 1;
    }

    /**
     * Get the cached list of nodes obtained from
     * the iterator so far.
     */
    private NodeVector getVector() {
      return m_vec2;
    }

    /**
     * Call this method with 'true' if the
     * iterator is exhausted and the cached list
     * is complete, or no longer growing.
     */
    private void setCacheComplete(boolean b) {
      m_isComplete2 = b;

    }

    /**
     * Returns true if no cache is complete
     * and immutable.
     */
    private boolean isComplete() {
      return m_isComplete2;
    }
  }

  /**
   * Get the cached list of nodes appended with
   * values obtained from the iterator as
   * a NodeSequence is walked when its
   * nextNode() method is called.
   */
  protected IteratorCache getIteratorCache() {
    return m_cache;
  }
}
